\documentclass[E:/GsjzTle/main/main.tex]{subfiles}

\begin{document}

\texttt{1.T\ x}：在文章末尾打下一个小写字母 \(x\)\\
\texttt{2.U\ x}：撤销最后的 \(x\) 次修改操作\\
\texttt{3.U\ x}：询问当前文章中第 \(x\) 个字母并输出（注意 \(Q\)
操作并不算修改操作）

\begin{lstlisting}
const int N = 3e5 + 10;
struct Ctree{
	int l , r , sum;
}tree[N * 40];
int root[N] , Ctot;
void update(int l , int r , int pre , int &now , int pos)
{
	tree[++ Ctot] = tree[pre];
	tree[Ctot].sum ++ ;
	now = Ctot;
	if(l == r) return ;
	int mid = l + r >> 1;
	if(pos <= mid) update(l , mid , tree[pre].l , tree[now].l , pos);
	else update(mid + 1 , r , tree[pre].r , tree[now].r , pos);
}
int query(int l , int r , int rt , int k)
{
	if(l == r) return l;
	int sum1 = tree[tree[rt].l].sum , sum2 = tree[tree[rt].r].sum;
	int mid = l + r >> 1;
	if(k <= sum1) return query(l , mid , tree[rt].l , k);
	else return query(mid + 1 , r , tree[rt].r , k - sum1);
}
vector<int>vec;
int q , y;
char op , x , mp[N];
signed main()
{	
	vec.pb(0);
	cin >> q;
	rep(i , 1 , q)
	{
		cin >> op;	
		if(op == 'T')
		{
			cin >> x;
			update(1 , q , root[i - 1] , root[i] , i) , vec.pb(i) , mp[i] = x;
		}
		else if(op == 'U') 
		{
			cin >> y;
			int n = vec.size() - 1;
			root[i] = root[vec[n - y]];
			vec.pb(i);
		}
		else 
		{
			cin >> y;
			root[i] = root[i - 1];
			cout << mp[query(1 , q , root[i] , y)] << '\n';
		}
	}
	return 0;
}
\end{lstlisting}

\end{document}
